# 62. 不同路径
def unique_paths(m, n):
    """
    :type m: int 网格的宽度
    :type n: int 网格的高度
    :rtype: int 总共的路径
    """
    # 初始化一个二维数组，长度为m，高度为n+1
    # 设置好初始值为1
    dp = [[0] * m] * (n + 1)
    dp[0][0] = 1
    # 第0列的数据，路径都是1
    for row in range(1, n + 1):
        for column in range(0, m):
            if column == 0:
                dp[row][column] = 1
            else:
                dp[row][column] = dp[row][column - 1] + dp[row - 1][column]
    # 返回右下角的值
    return dp[-1][-1]


total_paths = unique_paths(7, 3)
print(total_paths)
total_paths = unique_paths(1, 1)
print(total_paths)
